import java.util.*;

/**
 * 1030. 距离顺序排列矩阵单元格
 * https://leetcode-cn.com/problems/matrix-cells-in-distance-order/
 */
public class Solutions_1030 {
    public static void main(String[] args) {
//        int R = 1, C = 2, r0 = 0, c0 = 0;  // output: {{0, 0}, {0, 1}}

//        int R = 2, C = 2, r0 = 0, c0 = 1;
        // output: {{0, 1}, {0, 0}, {1, 1}, {1, 0}}

        int R = 2, C = 3, r0 = 1, c0 = 2;
//         output: {{1, 2}, {0, 2}, {1, 1}, {0, 1}, {1, 0}, {0, 0}}

        int[][] result = allCellsDistOrder2(R, C, r0, c0);
        System.out.println(Arrays.deepToString(result));
    }

    /**
     * 解法二：优先队列（30ms）
     */
    public static int[][] allCellsDistOrder2(int R, int C, int r0, int c0) {
        Queue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                // 前减后，升序
                int x1 = Math.abs(o1[0] - r0) + Math.abs(o1[1] - c0);
                int x2 = Math.abs(o2[0] - r0) + Math.abs(o2[1] - c0);
                return x1 - x2;
            }
        });
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                queue.add(new int[]{i, j});
            }
        }
        int[][] res = new int[queue.size()][];
        int idx = 0;
        // 必须从优先队列中依次弹出栈顶元素，才能保证元素有序
        // 直接用 queue.toArray(res) 无法保证元素有序的
        while (!queue.isEmpty()) {
            res[idx++] = queue.poll();
        }
        return res;
    }

    /**
     * 解法一：广度优先搜索-bfs（10ms）
     * 以 [r0, c0] 为中心向四周扩展，每扩展一层，
     * 曼哈顿距离越大，且那一层的全部坐标，到 [r0, c0] 的距离都相等
     */
    public static int[][] allCellsDistOrder(int R, int C, int r0, int c0) {
        Queue<int[]> queue = new LinkedList<>();
        boolean[][] visited = new boolean[R][C];
        queue.add(new int[]{r0, c0});
        // 上、下、左、右
        int[][] direct = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        visited[r0][c0] = true;
        int[][] res = new int[R * C][2];
        int index = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] arr = queue.poll();
                res[index++] = arr;

                for (int[] dir : direct) {
                    int x = arr[0] + dir[0];
                    int y = arr[1] + dir[1];
                    // 在 [0, 0]，[R - 1, C - 1] 范围内，且未被访问过时，记录到队列中
                    if (x >= 0 && y >= 0 && x < R && y < C && !visited[x][y]) {
                        queue.add(new int[]{x, y});
                        // 标记为已访问
                        visited[x][y] = true;
                    }
                }
            }
        }
        return res;
    }
}
